// ----------------------------------------------------------------------------
/**
	File: fibonacci.cpp
	Author: Zef RosnBrick
	Archive: 
	Problem Number: 
*/
// ----------------------------------------------------------------------------

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int P[2][2];
void pow(int M[][2], int R[][2], int p)
{
	if (p == 0)
	{
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				R[i][j] = i == j;
		return;
	}

	pow(M, R, p / 2);

	fill(P[0], P[2], 0);
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				P[i][j] = (P[i][j] + R[i][k] * R[k][j]) % 10000;

	fill(R[0], R[2], 0);
	if (p % 2 == 0)
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				R[i][j] = P[i][j];
	else
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int k = 0; k < 2; k++)
					R[i][j] = (R[i][j] + P[i][k] * M[k][j]) % 10000;
}

int main()
{
	int caseno = 0, n, M[2][2], R[2][2];
	
	while (++caseno)
	{
		if (!(cin >> n) || n == -1)
			return 0;

		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				M[i][j] = i == 0 || j == 0;

		pow(M, R, n);

		printf("%i\n", R[0][1]);
	}
}
